Expand description
slotmap
This library provides a container with persistent unique keys to access
stored values, SlotMap
. Upon insertion a key is returned that can be
used to later access or remove the values. Insertion, removal and access all
take O(1) time with low overhead. Great for storing collections of objects
that need stable, safe references but have no clear ownership otherwise,
such as game entities or graph nodes.
The difference between a BTreeMap
or HashMap
and a slot map is
that the slot map generates and returns the key when inserting a value. A
key is always unique and will only refer to the value that was inserted.
A slot map’s main purpose is to simply own things in a safe and efficient
manner.
You can also create (multiple) secondary maps that can map the keys returned
by SlotMap
to other values, to associate arbitrary data with objects
stored in slot maps, without hashing required - it’s direct indexing under
the hood.
The minimum required stable Rust version for this crate is 1.49.
Examples
let mut sm = SlotMap::new();
let foo = sm.insert("foo"); // Key generated on insert.
let bar = sm.insert("bar");
assert_eq!(sm[foo], "foo");
assert_eq!(sm[bar], "bar");
sm.remove(bar);
let reuse = sm.insert("reuse"); // Space from bar reused.
assert_eq!(sm.contains_key(bar), false); // After deletion a key stays invalid.
let mut sec = SecondaryMap::new();
sec.insert(foo, "noun"); // We provide the key for secondary maps.
sec.insert(reuse, "verb");
for (key, val) in sm {
println!("{} is a {}", val, sec[key]);
}
Serialization through serde
, no_std
support and unstable features
Both keys and the slot maps have full (de)seralization support through
the serde
library. A key remains valid for a slot map even after one or
both have been serialized and deserialized! This makes storing or
transferring complicated referential structures and graphs a breeze. Care has
been taken such that deserializing keys and slot maps from untrusted sources
is safe. If you wish to use these features you must enable the serde
feature flag for slotmap
in your Cargo.toml
.
slotmap = { version = "1.0", features = ["serde"] }
This crate also supports no_std
environments, but does require the
alloc
crate to be available. To enable this you have to disable the
std
feature that is enabled by default:
slotmap = { version = "1.0", default-features = false }
Unfortunately SparseSecondaryMap
is not available in no_std
, because
it relies on HashMap
. Finally the unstable
feature can be defined to
enable the parts of slotmap
that only work on nightly Rust.
Why not index a Vec
, or use slab
, stable-vec
, etc?
Those solutions either can not reclaim memory from deleted elements or
suffer from the ABA problem. The keys returned by slotmap
are versioned.
This means that once a key is removed, it stays removed, even if the
physical storage inside the slotmap is reused for new elements. The key is a
permanently unique* reference to the inserted value. Despite
supporting versioning, a SlotMap
is often not (much) slower than the
alternative, by internally using carefully checked unsafe code. Finally,
slotmap
simply has a lot of features that make your life easy.
Performance characteristics and implementation details
Insertion, access and deletion is all O(1) with low overhead by storing the
elements inside a Vec
. Unlike references or indices into a vector,
unless you remove a key it is never invalidated. Behind the scenes each
slot in the vector is a (value, version)
tuple. After insertion the
returned key also contains a version. Only when the stored version and
version in a key match is a key valid. This allows us to reuse space in the
vector after deletion without letting removed keys point to spurious new
elements. *After 231 deletions and insertions to the
same underlying slot the version wraps around and such a spurious reference
could potentially occur. It is incredibly unlikely however, and in all
circumstances is the behavior safe. A slot map can hold up to
232 - 2 elements at a time.
The memory usage for each slot in SlotMap
is 4 + max(sizeof(T), 4)
rounded up to the alignment of T
. Similarly it is 4 + max(sizeof(T), 12)
for HopSlotMap
. DenseSlotMap
has an overhead of 8 bytes per element
and 8 bytes per slot.
Choosing SlotMap
, HopSlotMap
or DenseSlotMap
A SlotMap
is the fastest for most operations, except iteration. It can
never shrink the size of its underlying storage, because it must remember
for each storage slot what the latest stored version was, even if the slot
is empty now. This means that iteration can be slow as it must iterate over
potentially a lot of empty slots.
HopSlotMap
solves this by maintaining more information on
insertion/removal, allowing it to iterate only over filled slots by ‘hopping
over’ contiguous blocks of vacant slots. This can give it significantly
better iteration speed. If you expect to iterate over all elements in a
SlotMap
a lot, and potentially have a lot of deleted elements, choose
HopSlotMap
. The downside is that insertion and removal is roughly twice
as slow. Random access is the same speed for both.
DenseSlotMap
goes even further and stores all elements on a contiguous
block of memory. It uses two indirections per random access; the slots
contain indices used to access the contiguous memory. This means random
access is slower than both SlotMap
and HopSlotMap
, but iteration is
significantly faster, as fast as a normal Vec
.
Choosing SecondaryMap
or SparseSecondaryMap
You want to associate extra data with objects stored in a slot map, so you use (multiple) secondary maps to map keys to that data.
A SecondaryMap
is simply a Vec
of slots like slot map is, and
essentially provides all the same guarantees as SlotMap
does for its
operations (with the exception that you provide the keys as produced by the
primary slot map). This does mean that even if you associate data to only
a single element from the primary slot map, you could need and have to
initialize as much memory as the original.
A SparseSecondaryMap
is like a HashMap
from keys to objects, however
it automatically removes outdated keys for slots that had their space
reused. You should use this variant if you expect to store some associated
data for only a small portion of the primary slot map.
Custom key types
If you have multiple slot maps it’s an error to use the key of one slot map on another slot map. The result is safe, but unspecified, and can not be detected at runtime, so it can lead to a hard to find bug.
To prevent this, slot maps allow you to specify what the type is of the key
they return. You can construct new key types using the new_key_type!
macro. The resulting type behaves exactly like DefaultKey
, but is a
distinct type. So instead of simply using SlotMap<DefaultKey, Player>
you
would use:
new_key_type! { struct PlayerKey; }
let sm: SlotMap<PlayerKey, Player> = SlotMap::with_key();
You can write code generic over any key type using the Key
trait.
Modules
- Contains the slot map implementation.
- Contains the dense slot map implementation.
- Contains the faster iteration, slower insertion/removal slot map implementation.
- Contains the secondary map implementation.
- Contains the sparse secondary map implementation.
Macros
- A helper macro to create new key types. If you use a new key type for each slot map you create you can entirely prevent using the wrong key on the wrong slot map.
Structs
- The default slot map key type.
- Dense slot map, storage with stable unique keys.
- Hop slot map, storage with stable unique keys.
- The actual data stored in a
Key
. - Secondary map, associate data with previously stored elements in a slot map.
- Slot map, storage with stable unique keys.
- Sparse secondary map, associate data with previously stored elements in a slot map.
Traits
- Key used to access stored values in a slot map.